/**
 * Copyright (c) [2025] [何屹林]
 *
 * 保留所有权利。
 *
 * 文件名称：NFA_maker.h
 * 模块功能说明：
 * 该模块定义NFA内部各种结构体，定义生成NFA过程的各种函数，并构建NFA状态转移表，完成了NFA图生成状态转换表的函数和NFA图的生成工作。
 *
 * 华南师范大学-计算机学院-网络工程-1班
 * 作者：何屹林-20222132023
 * 完成日期：2025年7月24日
 */
#include "logic.h"

QStack<NFA*> NFAs;
int maxcode=-1;
QHash<int,NFA*>NFAHash;
QHash<NFA*,int>NFAHash2;
NFA_begin_end resultNFA;
QMap<int, NFAState> StateTable;
QVector<int> InsertOrder;
QSet<int> StartNFA;
QSet<int> EndNFA;
QMap<int, int> ExitNFA;

//下面开始生成NFA的工作

//（1）创建并记录NFA结点
NFA *newNFA(){
    NFA*x=new NFA;
    x->id=NfaCnt++;
    NFAs.push(x);
    NFAHash.insert(x->id,x);
    NFAHash2.insert(x,x->id);
    return x;
}

//(2)释放所有的NFA结点
void Logic::delNFAs(){
    while(!NFAs.isEmpty())
    {
        delete NFAs.top();
        NFAs.pop();
    }
}

//创建基本字符NFA，建立基本的NFA模型，也就是建立一个新的NFA_begin_end
NFA_begin_end originNFA(const QChar&c){
    NFA*s=newNFA();
    NFA*e=newNFA();
    s->isStart=true;
    e->isEnd=true;
    Edge edge;
    edge.c=c;
    edge.next=e;
    s->edges.push_back(edge);
    Chars.insert(c);
    return NFA_begin_end(s,e);
}

//处理连接运算符号
NFA_begin_end contact(NFA_begin_end&x,NFA_begin_end&y){
    x.end->isEnd=false;
    y.start->isStart=false;
    Edge edge;
    edge.c=EMPTY;//用空白边连接两个图即可，EMPTY代表eplsion
    edge.next=y.start;
    x.end->edges.push_back(edge);
    return NFA_begin_end(x.start,y.end);}

//处理选择运算符符号

NFA_begin_end select(NFA_begin_end &x,NFA_begin_end &y)
{
    NFA*ns=newNFA();
    NFA*ne=newNFA();
    x.start->isStart=false;
    y.start->isStart=false;
    x.end->isEnd=false;
    y.end->isEnd=false;
    ns->isStart=true;
    ne->isEnd=true;
    Edge edge1,edge2;
    edge1.c=EMPTY;
    edge1.next=x.start;
    ns->edges.push_back(edge1);
    edge2.c=EMPTY;
    edge2.next=y.start;
    ns->edges.push_back(edge2);
    Edge edge3,edge4;
    edge3.c=EMPTY;
    edge3.next=ne;
    x.end->edges.push_back(edge3);
    edge4.c=EMPTY;
    edge4.next=ne;
    y.end->edges.push_back(edge4);
    return NFA_begin_end(ns,ne);

}


//处理*运算符
NFA_begin_end circle(NFA_begin_end&x)
{
    NFA*ns=newNFA();
    NFA*ne=newNFA();
    x.start->isStart=false;
    x.end->isEnd=false;
    ns->isStart=true;
    ne->isEnd=true;
    Edge edge1;
    edge1.c=EMPTY;
    edge1.next=x.start;
    ns->edges.push_back(edge1);
    Edge edge2;
    edge2.c=EMPTY;
    edge2.next=ne;
    x.end->edges.push_back(edge2);
    Edge edge3;
    edge3.c=EMPTY;
    edge3.next=ns;
    ne->edges.push_back(edge3);
    Edge edge4;
    edge4.c=EMPTY;
    edge4.next=ne;
    ns->edges.push_back(edge4);
    return NFA_begin_end(ns,ne);
}


//处理？可选运算符
NFA_begin_end option(NFA_begin_end &x)
{
    NFA*ns=newNFA();
    NFA*ne=newNFA();
    x.start->isStart=false;
    x.end->isEnd=false;
    ns->isStart=true;
    ne->isEnd=true;
    Edge edge1;
    edge1.c=EMPTY;
    edge1.next=x.start;
    ns->edges.push_back(edge1);
    Edge edge2;
    edge2.c=EMPTY;
    edge2.next=ne;
    x.end->edges.push_back(edge2);
    Edge edge3;
    edge3.c=EMPTY;
    edge3.next=ne;
    ns->edges.push_back(edge3);
    return NFA_begin_end(ns,ne);
}


//使用DFS算法生成状态转换表
void buildNFAStateTable()
{
    QStack<NFA*>nfaStack;//在成图之前，NFA栈存放着一个个被连接符分开的小图，当遇到连接符时就调出对应数量的图进行处理再压回
    QSet<NFA*>nfaVisited;//记录已经被访问过的NFA图
    //初态
    NFA*s=resultNFA.start;
    NFAState startState;//起始状态
    startState.flag='i';//in表示初态；
    //为状态转换表赋初值
    startState.id=s->id;
    StateTable[s->id]=startState;
    InsertOrder.push_back(s->id);
    StartNFA.insert(s->id);
    nfaStack.push(s);
    //遍历nfa栈中的每一个图
    while(!nfaStack.isEmpty())
    {
        NFA*x=nfaStack.top();//取出栈顶
        nfaStack.pop();//删除栈顶
        nfaVisited.insert(x);//记录栈顶
        //对于被取出的这个nfa（标记为x），遍历他的边集；对于每一条边，记录并生成对应的状态转换
        for(const Edge&edge :x->edges)
        {
            QChar inputChar=edge.c;
            NFA*y=edge.next;
            //记录状态转换信息、
            StateTable[x->id].char2state[inputChar].insert(y->id);
            //如果下一个状态没有被访问过，，那就将它加入nfa栈中
            if(!nfaVisited.contains(y))
            {
                nfaStack.push(y);
                //同上，入栈之后要记录它的状态信息
                NFAState nextState;
                nextState.id=y->id;
                //接下来，看这个新状态是否为初态，终态，退出态
                if(y->isStart)
                {
                    nextState.flag='i';//in表示初态
                    StartNFA.insert(nextState.id);
                }
                if(y->isEnd)
                {
                    nextState.flag='o';//out表示终态
                    EndNFA.insert(nextState.id);
                }
                if(y->isExit)
                {
                    //nextState.flag='m';//mid中止表示退出态
                    ExitNFA[nextState.id]=y->cd;//退出态赋给对应单词编码
                    if(y->cd>maxcode)
                    {
                        maxcode=y->cd;
                    }
                }
                StateTable[y->id]=nextState;
                if(!y->isEnd)
                {
                    InsertOrder.push_back(y->id);
                }
            }
        }
    }
    //遍历完毕插入终态
    NFA*endNode=resultNFA.end;
    InsertOrder.push_back(endNode->id);
}





//正则转NFA
void Logic::buildNFA()
{
    //利用双栈法，一个存放NFA，一个存放运算符号。首先要对表达式做逆波兰处理（后缀表达形式）
    QStack<QChar> opStack;//存放运算符
    QStack<NFA_begin_end> beNFAStack;//存放小型NFA图（用记录起始结点对的形式存储）
    //将已经被presolve过的正则表达式进行逆波兰处理
    //优先级情况先前已经有定义：OpPrec{{'|',1},{'@',2},{'*',3},{'?',4}};
    for(const QChar&c:resultText)
    {

        switch(char(c.unicode()))
        {
        case' '://空格直接跳过即可，正常来讲不会有空格，以防万一
            break;
        case'(':
            opStack.push(c);//左括号直接入op栈即可
            break;
        case')':
        {
            //右括号要及时处理其之前到左括号之间的内容
            //按照括号内的内容构建NFA
            while((!opStack.isEmpty())&&(opStack.top()!='('))
            {
                //从运算符栈一个个取出运算符，直到遇见左括号为止
                QChar op=opStack.top();
                opStack.pop();
                //此时只需考虑连接和选择两种运算可能，因为我们已经完成预处理，此处不可能出现？和*
                //从NFA栈中取出两个子图NFA
                NFA_begin_end y=beNFAStack.top();
                beNFAStack.pop();
                NFA_begin_end x=beNFAStack.top();
                beNFAStack.pop();
                if((op=='|')||(op=='@'))
                {
                    beNFAStack.push(op=='|'?select(x,y):contact(x,y));
                }
            }
            if(opStack.isEmpty())
            {
                qDebug()<<"括号未闭合，输出错误信息";
                exit(2);            }
            else
                opStack.pop();//否则说明遇到左括号了，结束
            break;
        }
        case'|':
        case'@':
            //处理运算符|和@
            while((!opStack.isEmpty())&&(opStack.top()=='|'||opStack.top()=='@')&&(OpPrec[opStack.top()]>=OpPrec[c]))
            {
                QChar op=opStack.top();
                opStack.pop();
                //从NFA栈中取出两个子图NFA
                NFA_begin_end y=beNFAStack.top();
                beNFAStack.pop();
                NFA_begin_end x=beNFAStack.top();
                beNFAStack.pop();
                beNFAStack.push(op=='|'?select(x,y):contact(x,y));

            }
            //?
            opStack.push(c);
            break;


        case'?':
        case'*':
            //处理闭包和可选运算符号
            //从NFA栈中取出一个NFA即可
            if(!beNFAStack.isEmpty())
            {
                NFA_begin_end tt=beNFAStack.top();
                beNFAStack.pop();
                beNFAStack.push((c=='?')?option(tt):circle(tt));

            }
            else{
                qDebug()<<"正则表达式语法错误，单目运算符未能匹配到NFA";
                exit(3);
            }
            break;
            //EXIT这里
        case EXIT:
        {
            if(!beNFAStack.isEmpty())//退出符号对应动作生成最后的单词并编码
            {
                NFA_begin_end tt=beNFAStack.top();
                beNFAStack.pop();
                tt.end->cd=CdCnt++;
                tt.end->isExit=true;
                beNFAStack.push(tt);

            }
            break;
        }
        default: //处理字母类
            beNFAStack.push(originNFA(c));


        }
    }
    //处理栈中剩余的运算符号
    while(!opStack.isEmpty())
    {
        QChar op=opStack.top();
        opStack.pop();
        if(op=='|'||op=='@')
        {
            if(beNFAStack.size()<2)
            {
                qDebug()<<"双目运算符匹配不到两个NFA";
                exit(4);
            }
            NFA_begin_end y=beNFAStack.top();
            beNFAStack.pop();
            NFA_begin_end x=beNFAStack.top();
            beNFAStack.pop();
            beNFAStack.push((op=='|')?select(x,y):contact(x,y));

        }
        else
            //resultText+=op;
            // qDebug()<<op;
            //     qDebug()<<"有未知的运算符号";
            exit(5);
    }
    //处理到最后NFA栈中只有一个NFA，也就是最终的NFA图
    resultNFA=beNFAStack.top();
    //NFA图成功生成
    buildNFAStateTable();
    //状态转换表生成
}

//生成NFA图
void Logic::genNFA()
{
    QVector<QString> headers{"状态","ID","ε"};//设置表头
        int colCnt=headers.size();
    QMap<QChar,int>charCol{{EMPTY,colCnt-1}};
    for(const auto&c:Chars)
    {
        if(C2S.contains(c))
        {headers.push_back(trim(C2S[c]));}
        else
        {headers.push_back(c==ANY?"ANY":STR(c));}
        charCol[c]=colCnt++;
    }
    int rowCnt=StateTable.size()+1;
    NFATable.resize(rowCnt,QVector<QString>(colCnt));
    NFATable[0]=headers;
    int row=1;
    for (const auto& id : InsertOrder) {
        const NFAState& node = StateTable[id];
        NFATable[row][0] = node.flag;  // Flag 列
        NFATable[row][1] = QString::number(node.id);  // ID 列
        for (auto entry=node.char2state.begin();entry!=node.char2state.end();++entry)
        {NFATable[row][charCol[entry.key()]] = set2string(entry.value());}
        ++row;
    }
}

//创建表格显示NFA
void Logic::NFATableShow(const QString& title) {

    QStringList colHeader,header;
    for(int i=1;i<=NFATable.size();i++)
        colHeader.append(QString::number(i));

    for(int i=1;i<=NFATable[0].size();i++)
        header.append(QString::number(i));

    formShow(title,header,colHeader,NFATable);
    return;
}
